package com.leecode.answer;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    /**
     * leecode 判断二分图地址：https://leetcode-cn.com/problems/is-graph-bipartite/
     * 网络上说是采用染色法,其实跟我想法本质一样，前者是标记，我的方法是判断是否已存在，代码多了一些，但是不难理解
     * 思路，对于输入的二维数组，我采用桶来装一位数据，比如：
     * 入参： [[1,3], [0,2], [1,3], [0,2]]
     * 可以 转化为：
     *  3    2    3    2
     *  1    0    1    0
     * ---,----,----,----
     *  0    1    2    3
     *
     *  那么只需要遍历每一个桶，如果 把桶的下标视为左键，桶里的每个值视为右键
     *  那么可以新增两个map集合，一个专门存储 左键 --- mapl，一个专门存储 右键 --- mapr，
     *  mapc存储只针对key，value随便，大比分 mapl.put( leftKey,1),其中1 就是写死而已，没用处
     *  遍历中用到了一个for循环，for循环里有调用递归方法
     *  1. for循环是为了遍历桶，
     *  2. 递归是为了把某个桶里的值，当作下标再次调用自身
     *  然后就是依次遍历，从第一个桶，往右遍历，把遇到的桶的下标（左键），桶里的值（右键）存入mapl,mapr
     *  如果过程中发现，待存入的值在map中已存在，那么就是false
     *  如果执行到底都很顺利，那么就返回true
     * @param args
     */
    public static void main(String[] args) {
        Solution solution = new Solution();
        int brr[][] = new int[][]{
                new int[]{},
                new int[]{2,4,6},
                new int[]{1,4,8,9},
                new int[]{7,8},
                new int[]{1,2,8,9},
                new int[]{6,9},
                new int[]{1,5,7,8,9},
                new int[]{3,6,9},
                new int[]{2,3,4,6,9},
                new int[]{2,4,5,6,7,8},

        };
// [[4],[],[4],[4],[0,2,3]]
        System.out.println(solution.isBipartite(brr));
    }

    public boolean find(List<List<Integer>>  list1,int findIndex,Map<Integer,Integer> mapl,Map<Integer,Integer> mapr){

        List<Integer> list = list1.get(findIndex);
        if(list.size() == 0){
            return true;
        }

        for (int i = 0; i < list.size(); i++) {
            int number = list.get(i);

            {
                int left = findIndex;
                int right = number;
                if ((mapl.containsKey(left) && mapr.containsKey(right)) || (mapl.containsKey(right) && mapr.containsKey(left))) {
                    continue;
                }

                if ((mapr.containsKey(left) && mapr.containsKey(right)) || (mapl.containsKey(left) && mapl.containsKey(right))) {
                    return false;
                }


                if (mapr.containsKey(left)) {
                    mapl.put(right, 1);
                } else if (mapl.containsKey(right)) {
                    mapr.put(left, 1);
                } else {
                    mapl.put(left, 1);
                    mapr.put(right, 1);
                }
            }

            boolean status = find(list1,number,mapl,mapr);
            if(!status){
                return status;
            }
        }
        return true;
    }


    public boolean isBipartite(int[][] graph) {
        Map<Integer,Integer> mapl = new HashMap<>();
        Map<Integer,Integer> mapr = new HashMap<>();

        List<List<Integer>>  list1 = new ArrayList<>();


        int count = 0;
        for (int i = 0; i < graph.length; i++) {
            int[] arr = graph[i];
            List<Integer>  list2 = new ArrayList<>();
            for (int j = 0; j < arr.length; j++) {
                list2.add(arr[j]);
                count++;
            }

            list1.add(list2);

        }
        for (int i = 0; i < list1.size(); i++) {
            boolean status = find(list1,i,mapl,mapr);
            if(!status) {
                return false;
            }

        }
        return true;
    }
}
